# Sharif University CTF 2016: High-speed RSA Keygen [Part1]
# Filename: solver.sage

from sage.all import *

def get_primes(n):
	numbers = set(range(n, 1, -1))
	primes = []
	while numbers:
		p = numbers.pop()
		primes.append(p)
		numbers.difference_update(set(range(p*2, n+1, p)))
	return primes

def coppersmith(pbar):
	global n
	beta = 0.5
	epsilon = beta^2/7

	pbits = 1024
	kbits = floor(n.nbits()*(beta^2-epsilon))
	PR.<x> = PolynomialRing(Zmod(n))
	f = x + pbar

	x0 = f.small_roots(X=2^kbits, beta=beta)  # find root < 2^kbits with factor >= n^0.3

	if len(x0) > 0:
		return x0[0] + pbar
	else:
		return None



####### main #######
n = 0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB
e = 65537
c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B

primes = get_primes(443)
primes.sort()
del primes[0]

pi = 1;
for x in primes:
        pi *= x
# print "pi=%X" % pi

for i in range(1,4096):
        print i
        kp = (i + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19)
        pbar = kp * pi * (2**400)
        # High-bit known attack
        p = coppersmith(pbar)
        if p != None and n % p == 0:
                print "Found"
                print "p", p
                break


# Result
# > sage solver.sage
# Found
# p 144299940222848685214153733110344660304144248927927225494186904499495592842937728938865184611511914233674465357703431948804720019559293726714685845430627084912877192848598444717376108179511822902563959186098293320939635766298482099885173238182915991321932102606591240368970651488289284872552548559190434607447

